186. Египетские знаки

Прошлым летом школьник Вася побывал в Египте. И лишь сейчас он вспомнил, что во время своей поездки он успел сфотографировать много интересного. Перебирая эти фотографии, больше всего он заинтересовался видами пирамид в Гизе. Пирамиды, помимо всяких иероглифов, содержали удивительные знаки – 1, 2, 3, 4, 5, 6, 7, 8, 9, 0. Внимательно присмотревшись, Вася заметил, что каждая строка таких странных символов является степенью двойки и более того: первая строка начинается последовательностью символов 1, вторая - 2, ..., сто двадцатая - 120, и т.д. Все было бы хорошо, если бы Вася пользовался современными фотоаппаратами, но так как его старенькая мыльница плохо сфотографировала наиболее освещенные части пирамиды, то все символы разобрать невозможно и поэтому определить показатель степени двойки, соответствующий таким строкам, затруднительно. Вася задумался о восстановлении символов и, наконец, решил попросить кого-нибудь написать программу (Вася учится в 6 классе и не знает языков программирования), которая бы определила показатель степени двойки, которая записана в n-ой строке.

Вход. Единственное число n (n ≤ 10⁷).

Выход. Выведите минимальное натуральное число k такое, что два в степени k в десятичной записи начинается c числa n. Если Вася что-то напутал, и такого числа нет, то выведите -1.

Пример входа	Пример выхода
12	7

РЕШЕНИЕ

математика

Анализ алгоритма

Будем моделировать процесс возведения двойки в степень до тех пор пока не встретится такое k, что два в степени k в десятичной записи начинается с числа n. Это случится всегда для любого n.

Присвоим действительной переменной d значение 1. Будем ее умножать на два, при этом каждый раз совершая следующие действия:

· если целая часть числа d равна n, то искомая степень двойки найдена.

· если значение d больше n, то разделим d на 10.

При этом остается подсчитать количество умножений начального значения d на 2 – это и будет искомая степень k.

Пример

Промоделируем изменение переменных на примере n = 12.

d	res	комментарий
1.0	0
2.0	1
4.0	2
8.0	3
16.0 → 1.6	4	16.0 > n, делим на 10
3.2	5
6.4	6
12.8	7	целая часть 12.8 равна n, стоп

Реализация алгоритма

В переменной res будем подсчитывать степень двойки.

int res = 0;

double d = 1.0;

scanf("%d",&n);

while(1)

{

d = d * 2; res++;

if((int)(d+0.001) == n) break;

if(d > n) d = d / 10;

}

printf("%d\n",res);

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int res = 0, n = con.nextInt();

double d = 1;

while(true)

{

d *= 2; res++;

if (n == (int)d) break;

if(d > n) d = d / 10;

}

System.out.println(res);

}

}